package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/remove-duplicates-from-an-unsorted-linked-list'>从未排序的链表中移除重复元素(Remove Duplicates From an Unsorted Linked List)</a>
 * <p>给定一个链表的第一个节点 head ，找到链表中所有出现多于一次的元素，并删除这些元素所在的节点。</p>
 * <p>返回删除后的链表。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1:
 *      输入: head = [1,2,3,2]
 *      输出: [1,3]
 *      解释: 2 在链表中出现了两次，所以所有的 2 都需要被删除。删除了所有的 2 之后，我们还剩下 [1,3] 。
 *
 *  示例 2:
 *      输入: head = [2,1,1,2]
 *      输出: []
 *      解释: 2 和 1 都出现了两次。所有元素都需要被删除。
 *
 *  示例 3:
 *      输入: head = [3,2,2,1,3,2,4]
 *      输出: [1,4]
 *      解释: 3 出现了两次，且 2 出现了三次。移除了所有的 3 和 2 后，我们还剩下 [1,4] 。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>链表中节点个数的范围是 [1, 10^5]</li>
 *     <li>1 <= Node.val <= 10^5</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/5/9 17:38
 */
public class LC1836RemoveDuplicatesFromAnUnSortedLinkedList_M {
    static class Solution {
        public ListNode deleteDuplicatesUnsorted(ListNode head) {
            int[] helper = new int[100001];
            ListNode currNode = head;
            while (currNode != null) {
                helper[currNode.val]++;
                currNode = currNode.next;
            }
            ListNode dummyHead = new ListNode(-1, head);
            currNode = dummyHead;
            while (currNode.next != null) {
                if (helper[currNode.next.val] > 1) {
                    currNode.next = currNode.next.next;
                } else {
                    currNode = currNode.next;
                }
            }
            return dummyHead.next;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printListNode(solution.deleteDuplicatesUnsorted(Generator.create(1, 2, 3, 2)));
        Printer.printListNode(solution.deleteDuplicatesUnsorted(Generator.create(2, 1, 1, 2)));
        Printer.printListNode(solution.deleteDuplicatesUnsorted(Generator.create(3, 2, 2, 1, 3, 2, 4)));
    }
}
